from LL import Node

class Sorted(object):
	def __init__(self):
		self._head = None
		self._sz = 0
	def __len__(self):
		return self._sz
	def __str__(self):
		if self._head==None:
			return "*"
		else:
			return str(self._head)
	def insert(self, v):
		if self._head==None or v<self._head.v:
			self._head = Node(v, self._head)
		else:
			p = self._head
			while p.nx!=None and p.nx.v<v:
				p = p.nx
			p.nx = Node(v, p.nx)
		self._sz += 1

class SortedSentinel(object):
	def __init__(self):
		self._head = Node(float("inf"), None)
		self._sz = 0
	def __len__(self):
		return self._sz
	def __str__(self):
		return str(self._head)
	def insert(self, v):
		if v<self._head.v:
			self._head = Node(v, self._head)
		else:
			p = self._head
			while p.nx.v<v:
				p = p.nx
			p.nx = Node(v, p.nx)
		self._sz += 1

class SortedTester(object):
	def __init__(self):
		self._normal = Sorted()
		self._sentinel = SortedSentinel()
	def __len__(self):
		return len(self._normal)
	def __str__(self):
		return "normal: "+str(self._normal)+"\nsentinel: "+str(self._sentinel)
	def insert(self, v):
		self._normal.insert(v)
		self._sentinel.insert(v)

l = SortedTester()
l.insert(19)
l.insert(1)
l.insert(-2)
l.insert(7)
l.insert(42)
print l
